package lhc.alg.top100;

import java.util.HashMap;
import java.util.Map;

/**
 * description: https://leetcode.cn/problems/super-egg-drop/
 *  887 鸡蛋掉落 动归 嘶 没整明白啊 O（kn log n） O(kn)
 * author: hongchen.liao
 * date:  2022/8/31
 */
public class _887_Super_Egg_Drop {

    class Solution {
        Map<Integer, Integer> memo = new HashMap<>();
        public int superEggDrop(int k, int n) {
            return dp(k, n);
        }

        int dp(int k, int n){
            if(!memo.containsKey(n * 100 + k)){
                int ans = 0;
                if(n == 0){
                    ans = 0;
                }else if(k == 1){
                    ans = n;
                }else{
                    int low = 1, hi = n;
                    while(low + 1 < hi){
                        int x = (low + hi) / 2;
                        int t1 = dp(k-1, x-1);
                        int t2 = dp(k, n-x);

                        if(t1 < t2){
                            low = x;
                        }else if(t1 > t2){
                            hi = x;
                        }else{
                            low = hi = x;
                        }
                    }
                    ans = 1 + Math.min(Math.max(dp(k-1, low-1), dp(k, n-low)), Math.max(dp(k-1, hi-1), dp(k, n-hi)));

                }
                memo.put(n * 100 + k, ans);
            }
            return memo.get(n * 100 + k);
        }
    }

}
